//package org.cllib.tool;
//
//import java.util.ArrayList;
//import java.util.Arrays;
//import java.util.Comparator;
//import java.util.List;
//
//import org.cllib.ds.MinHeap;
//import org.eclipse.swt.graphics.Point;
//
//public class PathFinder implements Runnable {
//	final Point start;
//	final Point end;
//	
//	List<PathFinderListener> ls = new ArrayList<PathFinderListener>();
//	
//	public final static int STATUS_READY = 0;
//	public final static int STATUS_SEARCHING = 1;
//	public final static int STATUS_DONE = 2;
//	
//	int status = STATUS_READY;
//	
//	final Map map;
//	
//	List<PathElement> path = new ArrayList<PathElement>();
//	
//	boolean enableDiamond;
//	
//	Comparator<PathElement> c = new Comparator<PathElement>(){
//
//		public int compare(PathElement o1, PathElement o2) {
//			// TODO Auto-generated method stub
//			return o1.getF() - o2.getF();
//		}
//		
//	};
//	
//	MinHeap OPEN = new MinHeap(c);
//	MinHeap CLOSED = new MinHeap(c);
//	
//	public PathFinder(Map map , Point start , Point end){
//		this.map = map;
//		this.start = new Point(start.x , start.y);
//		this.end = new Point(end.x , end.y);
//	}
//	
//	public void startSearching(){
//		synchronized (this) {
//			if(status == STATUS_READY){
//				new Thread(this).start();				
//			}
//		}
//	}
//	
//	public void addPathFinderListener(PathFinderListener l){
//		if(!ls.contains(l)){
//			ls.add(l);			
//		}
//	}
//	
//	public void removePathFinderListener(PathFinderListener l){
//		ls.remove(l);
//	}
//	
//	public void run() {
//		// TODO Auto-generated method stub
//		synchronized (this) {
//			if(status == STATUS_READY){
//				status = STATUS_SEARCHING;
//				
//				OPEN.insert(new PathElement(start.x , start.y , null , 0 , Math.abs(end.x - start.x) + Math.abs(end.y - start.y)));
//				
//				while(!OPEN.isEmpty() && !isPathElementInHeap(end.x , end.y, OPEN)){
//					//tick
//					PathElement current = (PathElement)OPEN.extract();
//					
//					CLOSED.insert(current);
//					
//					final int cx = current.x;
//					final int cy = current.y;
//					
//					final int top = cy - 1;
//					final boolean topOK = top >= 0 && map.getDataAt(cx, top) != Map.BLOCK_OBSTACLE;
//					
//					if(topOK){
//						dealWithNeighbour(current, cx, top , 1);
//					}
//					
//					final int bottom = cy + 1;
//					final boolean bottomOK = bottom < map.getNumberOfRows() && map.getDataAt(cx, bottom) != Map.BLOCK_OBSTACLE;
//					
//					if(bottomOK){
//						dealWithNeighbour(current, cx, bottom , 1);
//					}
//					
//					final int left = cx - 1;
//					final boolean leftOK = left >= 0 && map.getDataAt(left, cy) != Map.BLOCK_OBSTACLE;
//					
//					if(leftOK){
//						dealWithNeighbour(current, left , cy , 1);						
//					}
//					
//					final int right = cx + 1;
//					final boolean rightOK = right < map.getNumberOfCols() && map.getDataAt(right, cy) != Map.BLOCK_OBSTACLE;
//					
//					if(rightOK){
//						dealWithNeighbour(current, right, cy , 1);
//					}
//					
//					if(leftOK || topOK){
//						final int leftTopX = cx - 1;
//						final int leftTopY = cy - 1;
//						
//						final boolean leftTopOK = leftTopX >= 0 && leftTopY >= 0 && map.getDataAt(leftTopX, leftTopY) != Map.BLOCK_OBSTACLE;
//						
//						if(leftTopOK){
//							dealWithNeighbour(current, leftTopX, leftTopY , 2);							
//						}
//					}
//					
//					if(rightOK || topOK){
//						final int rightTopX = cx + 1;
//						final int rightTopY = cy - 1;
//						
//						final boolean rightTopOK = rightTopY >= 0 && rightTopX < map.getNumberOfCols() && map.getDataAt(rightTopX, rightTopY) != Map.BLOCK_OBSTACLE;
//						
//						if(rightTopOK){
//							dealWithNeighbour(current, rightTopX, rightTopY , 2);	
//						}
//					}
//					
//					if(leftOK || bottomOK){
//						final int leftBottomX = cx - 1;
//						final int leftBottomY = cy + 1;
//						
//						boolean leftBottomOK = leftBottomY < map.getNumberOfRows() && leftBottomX >= 0 && map.getDataAt(leftBottomX, leftBottomY) != Map.BLOCK_OBSTACLE;
//						
//						if(leftBottomOK){
//							dealWithNeighbour(current,leftBottomX , leftBottomY , 2);
//						}
//					}
//					
//					if(rightOK || bottomOK){
//						final int rightBottomX = cx + 1;
//						final int rightBottomY = cy + 1;
//						
//						boolean rightBottomOK = rightBottomY < map.getNumberOfRows() && rightBottomX < map.getNumberOfCols() && map.getDataAt(rightBottomX, rightBottomY) != Map.BLOCK_OBSTACLE;
//						
//						if(rightBottomOK){
//							dealWithNeighbour(current, rightBottomX, rightBottomY , 2);
//						}
//					}
//					
//					notifyUpdatePath();
//					try {
//						Thread.sleep(100);
//					} catch (InterruptedException e) {
//						// TODO Auto-generated catch block
//						e.printStackTrace();
//					}
//				}
//				
//				if(OPEN.isEmpty()){
//					notifyFail();
//				}else{
//					PathElement pe = getPathElementFromHeap(OPEN, end.x, end.y);
//					while(pe != null){
//						path.add(pe);
//						
//						pe = pe.parent;
//					}
//					
//					notifySucceed();
//				}
//			}
//		}
//	}
//	
//	private void dealWithNeighbour(PathElement current , int nx, int ny , int c){
//		final int cost = current.g + c;
//		
//		if(isPathElementInHeap(nx, ny, OPEN)){
//			final PathElement npe = getPathElementFromHeap(OPEN, nx, ny);
//			if(cost < npe.g){
//				removePathElementFromHeap(OPEN, nx, ny);
//			}
//		}
//		
//		if(isPathElementInHeap(nx, ny, CLOSED)){
//			final PathElement npe = getPathElementFromHeap(CLOSED, nx, ny);
//			if(cost < npe.g){
//				removePathElementFromHeap(CLOSED, nx, ny);
//			}
//		}
//		
//		if(!isPathElementInHeap(nx, ny, OPEN) && !isPathElementInHeap(nx, ny, CLOSED)){
//			int h = Math.abs(end.x - nx) + Math.abs(end.y - ny);
//			
////			PathElement pe = new PathElement(nx , ny , current, cost , h);
////			PathElement pe = new PathElement(nx , ny , current, cost , 0);
//			PathElement pe = new PathElement(nx , ny , current, 0 , h);
//			OPEN.add(pe);
//		}
//	}
//	
//	private PathElement getPathElementFromHeap(MinHeap<PathElement> heap , int x, int y){
//		for(PathElement pe : heap) {
//			if(pe.x == x && pe.y == y){
//				return pe;
//			}
//		}
//		
//		return null;
//	}
//	
//	private void removePathElementFromHeap(MinHeap<PathElement> heap , int x, int y){
//		for(PathElement pe : heap) {
//			if(pe.x == x && pe.y == y){
//				heap.remove(pe);
//				return;
//			}
//		}
//	}
//	
//	private void notifyUpdatePath(){
//		for(PathFinderListener l : ls){
//			l.updatePath(this, Arrays.asList(OPEN.toArray(new PathElement[0])) , Arrays.asList(CLOSED.toArray(new PathElement[0])));
//		}
//	}
//	
//	private void notifyFail(){
//		for(PathFinderListener l : ls){
//			l.fail(this, Arrays.asList(OPEN.toArray(new PathElement[0])) , Arrays.asList(CLOSED.toArray(new PathElement[0])));
//		}
//	}
//	
//	private void notifySucceed(){
//		for(PathFinderListener l : ls){
//			l.succeed(this, path);
//		}
//	}
//	
//	private boolean isPathElementInHeap(int x, int y , MinHeap heap){
//		PathElement pe = new PathElement(x , y , null , -1 , -1);
//		return heap.contains(pe);
//	}
//}
